package 数据结构.章节09._148_双链表;

import 数据结构.章节09._145_基于数组实现线性表.MyList;

/**
 * @author 挚爱之夕
 * @date 2021/10/8 - 10 - 08 - 17:57
 * @Description: 数据结构.章节09._148_双链表
 * @Version: 1.0
 */
public class DoubleLinkedList<T> implements MyList<T> {
    protected final ListNode<T> first = new ListNode<T>(null);
    protected final ListNode<T> last = new ListNode<T>(null);
    protected int size = 0;

    public DoubleLinkedList() {
        //建立first和last之间的联系
        //first没有前驱，list没有后继
        first.next = last;
        last.pre = first;
    }
    //从尾部开始添加
    @Override
    public void add(T o) {
        ListNode<T> newNode = new ListNode<T>(o);
        last.pre.next = newNode;
        newNode.next = last;
        newNode.pre = last.pre;
        last.pre = newNode;
        size++;
    }

    @Override
    public void delete(T o) {
        ListNode<T> p = first.next;
        while (p != last) {   //到尾节点，哑元没有实际的数据意义
            if (p.data.equals(o)) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.next = null;  //赋值为null，使其快速成为垃圾回收对象
                p.pre = null;
                size--;
                break;
            }
            p = p.next;
        }
    }

    @Override
    public void delete(int index) {
        int i = 0;
        ListNode<T> p = first.next;
        while (p != last) {
            if (i == index) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.pre = null;
                p.next = null;
                size--;
                break;
            }
            i++;
            p = p.next;
        }
    }

    @Override
    public void modify(int index, T newElement) {
        if (index < 0 || index >= size) {   //什么也不做
            return;
        }
        int i = 0;
        ListNode<T> p = first.next;
        while (p != last) {
            if (i == index) {
                p.data = newElement;
                break;
            }
            i++;
            p = p.next;
        }
    }

    @Override
    public boolean contains(T o) {
        int index = find(o);
        return index>=0;
    }

    @Override
    public int find(T o) {
        int i = 0;
        ListNode<T> p = first.next;
        while(p != last){
            if(p.data.equals(o)){
                return i;
            }
            i++;
            p = p.next;
        }
        return -1;
    }

    @Override
    public T find(int index) {
        int i = 0;
        ListNode<T> p = first.next;
        while(p != last){
            if(i == index){
                return p.data;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode<T> p = first.next;
        while (p != last) {

            sb.append(p.data).append(p.next == last ? "" : " <-> ");
            p = p.next;
        }
        return sb.toString();
    }

    ListNode<T> now = first;
    @Override
    public boolean hasNext() {
        return now.next != last;
    }

    @Override
    public T next() {
        ListNode<T> next = now.next;
        now = next;
        return (T)next.data;
    }
}
